# 121. 买卖股票的最佳时机
# 给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。

# 不创建一维数组
def maxProfit(prices):
    """
    :type prices: List[int]
    :rtype: int
    """
    # 用来保存最大收益
    max_profit = 0
    # 用来保存最低价格
    min_price = prices[0]
    for index in range(1, len(prices) + 1):
        max_profit = max(max_profit, prices[index - 1] - min_price)
        min_price = min(min_price, prices[index - 1])
    return max_profit

# 使用动态规划的方式，需要创建一维数组
def maxProfit_create_list(prices):
    """
    :type prices: List[int]
    :rtype: int
    """
    # 初始化一个一维数组
    dp = [0 for _ in range(len(prices) + 1)]
    # 用来保存最低价格
    min_price = prices[0]
    for index in range(2, len(prices) + 1):
        dp[index] = max(dp[index - 1], prices[index - 1] - min_price)
        min_price = min(min_price, prices[index - 1])
    return dp[len(prices)]


# 暴力法，超时
def maxProfit_baoli(prices):
    """
    :type prices: List[int]
    :rtype: int
    """
    print(f"prices:{prices}")
    max_profit = 0
    prices_length = len(prices)
    for i in range(prices_length - 1):
        for j in range(i + 1, prices_length):
            max_profit = max(max_profit, prices[j] - prices[i])
    return max_profit


prices_1 = [7, 1, 5, 3, 6, 5]

result = maxProfit(prices_1)
print(f"result : {result}")
